import java.util.Arrays;

//大根堆
public class Heap {
    public  int[] heap;
    public  int usedSize;
    public Heap() {
        heap = new int[10];
    }

    //向下调整为堆
    //建堆的时间复杂度为O(n)
    public  void createHeap(int[] array) {
        heap = array;
        usedSize = array.length;

        //将数组调整为大根堆
        for (int i = (usedSize - 1 - 1)/2; i >= 0 ; i--) {
            siftDown(i,usedSize);
        }
    }

    public  boolean isFull() {
        return heap.length == usedSize;
    }

    /**
     *向下调整为堆
     *
     * @param parent 要调整子树的根节点
     * @param usedSize 调整的最终范围
     */

    public  void siftDown(int parent,int usedSize) {
        //判断parent的孩子是否在有效范围之内
        //parent的左孩子
        int child = 2 * parent + 1;

        //当parent的左孩子存在的时候
        while(child < usedSize) {
            //判断parent是否有右孩子
            if(child + 1 < usedSize && heap[child] < heap[child + 1]) {
                  child++;
            }

            //代码走到这里，child指向的是parent中值最大的孩子
            //判断是否需要调整
            if(heap[parent] < heap[child]) {
                swap(parent,child);
                //判断子树是否需要调整
                parent = child;
                child = 2 *parent + 1;
            }else {
                //不需要调整，直接退出循环
                break;
            }
        }
    }

    //重载siftDown方法，添加数组参数，使其变得灵活，降低解决Top K 问题的时间复杂度
    public void siftDown(int[] array,int parent,int usedSize) {
        //判断parent的左孩子是否在有效范围之内
        int child = 2 * parent + 1;
        //当parent的左孩子存在的时候
        while(child < usedSize) {
            //找出parent的右孩子，和左孩子比较大小
            if (child + 1 < usedSize && array[child + 1] > array[child]) {
                child++;
            }

            //判断parent和child的大小，判断是否需要调整
            if(array[parent] < array[child]) {
                swap(array,parent,child);
                //判断子树是否需要调整
                parent = child;
                child = 2 * child + 1;
            }else {
                //不需要调整直接退出循环
                break;
            }
        }
    }
    //重载swap方法，添加数组参数
    public void swap(int[] array,int i,int j) {
        assert i < array.length && j < array.length;
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    private  void siftUp() {
        //在堆顶插入元素之后向上调整为堆
        int cur = usedSize - 1;
        int parent = (cur - 1)/2;

        while(parent >= 0) {
            if(heap[parent] < heap[cur]) {
                swap(parent,cur);
                cur = parent;
                parent = (parent - 1)/2;
            }else {
                //不需要调整
                break;
            }
        }
    }

    public void swap(int i,int j) {
        int tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }

    //堆的插入：
    // 先判满，如果数组满了需要扩容
    //将要插入的元素放在堆底，然后通过调整，满足堆的性质
    public void grow() {
        heap = Arrays.copyOf(heap,2 * heap.length);
    }


    public void insert(int element) {
        if(isFull()) {
            grow();
        }
        //将元素插入到堆底
        heap[usedSize] = element;
        usedSize++;

        //将新的数组向上调整为堆
        siftUp();
    }

    //堆的删除：将堆顶元素和堆底元素进行交换
    //减少一个有效元素的个数
    //从上到下再次调整为堆
    public int delete() {
        //删除堆顶元素
        int last = usedSize - 1;
        int result = heap[0];
        swap(0,last);
        usedSize--;

        //将剩下的元素调整为大根堆
        //将数组向下调整为大根堆
        siftDown(0,usedSize);
        return result;
    }

    public int peek() {
        if(isEmpty()) {
            throw new RuntimeException("堆为空，无法找到堆顶元素");
        }

        return heap[0];
    }

    public boolean isEmpty() {
        return this.usedSize == 0;
    }
    public static void main(String[] args) {
        int[] array = new int[]{5,11,7,2,3,17};
        Heap heap1 = new Heap();
        heap1.createHeap(array);
        System.out.println(Arrays.toString(heap1.heap));
    }
}
